package backtrack

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/27 22:33
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type CombinationRepeatNum_BackTrack struct {
	array  []int
	target int
	result [][]int
}

func (m *CombinationRepeatNum_BackTrack) Method(array []int, target int) [][]int {
	if len(array) == 0 {
		return nil
	}
	m.result = make([][]int, 0)
	m.array = array
	m.target = target
	m.roll(0, 0, make([]int, 0))
	return m.result
}

func (m *CombinationRepeatNum_BackTrack) roll(depth, sum int, temp []int) {
	if sum == m.target {
		t := make([]int, len(temp), len(temp))
		copy(t, temp)
		m.result = append(m.result, t)
	}
	if sum > m.target {
		return
	}
	for i := depth; i < len(m.array); i++ {
		sum += m.array[i]
		temp = append(temp, m.array[i])
		m.roll(i, sum, temp)
		sum -= m.array[i]
		temp = temp[:len(temp)-1]
	}
}

func (m *CombinationRepeatNum_BackTrack) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{},
		Desc: &C.Desc{
			Name:        "CombinationRepeatNum_BackTrack",
			NameCn:      "",
			Description: "判断数组中是否存在这样几个数，使得和等于 target(数组元素 可以 无限重复的选择)",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}
